﻿//T1 二分查找 力扣
//思路：朴素二分查找
//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        int mid = 0;
//        while (left <= right)
//        {
//            mid = left + (right - left) / 2;//此处：防止出现left+right溢出int的情况
//            if (nums[mid] > target)
//                right = mid - 1;
//            else if (nums[mid] < target)
//                left = mid + 1;
//            else
//                return mid;
//        }
//        return -1;
//    }
//};

//总结：朴素二分查找模板
//while (left <= right)
//{
//    mid = left + (right - left) / 2;
//    if (---------)
//        right = mid - 1;
//    else if (---------)
//        left = mid + 1;
//    else
//        return ---------;
//}


//T2 在排序数组中查找元素的第一个和最后一个位置 力扣
//思路：使用二分查找，分别查找左右端点即可
//	注意事项：1.判断条件：left<right,因为当left=right时，说明已经找到结果了，
//				如果继续判断，则不会更新left或right，从而导致死循环。
//			2.求左端点：当nums[mid]<target，说明mid左边（包括mid）的值都不符合，left更新为mid+1
//					当nums[mid]=target时，由于可能出现多个target的情况，因此不能单独判断
//					因此将=和>合并比较，当nums[mid]>=target时，right更新为mid
//			3.mid：求法right=left+(right-left+1)/2 或者right = left+(right-left)/2
//				上述两种方法的区别是：left与right相邻时，mid更新为right所在的点/left所在的点
//				求左端点用right = left+(right-left)/2 右端点用right=left+(right-left+1)/2 
//			4.求右端点方法与左端点相反即可
//总结模板：
//	1.左端点：
//		while (left < right) {
//            mid = left + (right - left) / 2;
//            if (--------)
//                left = mid + 1;
//            else if (--------)
//                right = mid;
//            else
//                break;
//        }
//	2.右端点：
//		while (left < right) {
//            mid = left + (right - left + 1) / 2;
//            if (--------)
//                left = mid;
//            else if (--------)
//                right = mid - 1;
//            else
//                break;
//        }
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        if (nums.size() == 0)
//            return { -1, -1 };
//        int left = 0, right = nums.size() - 1;
//        // 左端点
//        int mid;
//        int ret_left = -1;
//        int ret_right = -1;
//        while (left < right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] < target)
//                left = mid + 1;
//            else if (nums[mid] >= target)
//                right = mid;
//            else
//                break;
//        }
//        if (nums[left] == target)
//            ret_left = left;
//        // 右端点
//        left = 0, right = nums.size() - 1;
//        while (left < right) {
//            mid = left + (right - left + 1) / 2;
//            if (nums[mid] <= target)
//                left = mid;
//            else if (nums[mid] > target)
//                right = mid - 1;
//            else
//                break;
//        }
//        if (nums[right] == target)
//            ret_right = right;
//        return { ret_left, ret_right };
//    }
//};


//T3 x的平方根 力扣
//思路：二分查找
//注意事项：不处理边界情况时，当right为int最大值时，right-0+1会溢出。
//			将right定义为long long类型效率会降低
//
//class Solution {
//public:
//    int mySqrt(int x) {
//        if (x < 1)
//            return 0;
//        int left = 1;
//        int right = x;
//        while (left < right) {
//            long long mid = left + (right - left + 1) / 2;
//            if (mid * mid <= x)
//                left = mid;
//            else
//                right = mid - 1;
//        }
//        return left;
//    }
//};

//T4 搜索插入位置 力扣
//思路：二分查找
//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] >= target)
//                right = mid;
//            else
//                left = mid + 1;
//        }
//        if (nums[left] < target)
//            return left + 1;
//        return left;
//    }
//};

//T5 山脉数组的峰顶索引 力扣
//思路：二分查找
//		该数组值的分布：^ （该形状）  因此：取中点，判断中点的值是否比前一个值大
//										如果大，则 left = mid；
//										如果小，则 right = mid-1；直到left=right
//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int left = 0, right = arr.size() - 1;
//        while (left < right) {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid - 1] < arr[mid])
//                left = mid;
//            else
//                right = mid - 1;
//        }
//        return left;
//    }
//};

//T6 寻找峰值 力扣
//思路：该题求出一个峰值即可，使用二分查找，思路同上题
//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] > nums[mid + 1])
//                right = mid;
//            else
//                left = mid + 1;
//        }
//        return left;
//    }
//};

//T7 搜索旋转排序数组中的最⼩值 力扣
//思路：二分查找
//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right) {
//            int mid = left + (right - left) / 2;
//            if (nums[right] < nums[mid])
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        return nums[left];
//    }
//};
//不同方法：每次比较都取最后边的值
//class Solution
//{
//public:
//	int findMin(vector<int>& nums)
//	{
//		int left = 0, right = nums.size() - 1;
//		int x = nums[right]; // 标记⼀下最后⼀个位置的值
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] > x) left = mid + 1;
//			else right = mid;
//		}
//		return nums[left];
//	}
//};

//T8 0〜n-1中缺失的数字 力扣
//思路：
//	1.哈希：填哈希表，看哪个没有填
//	2.遍历：直接找
//	3.位运算：^ 异或一个不缺数字的数组，结果即为要找的数
//	4.数学（高斯求和公式）：等差求和公式（不缺少的）减去当前数组和
//	------------以上 O（N）-------------
//	5.二分：如下
//class Solution {
//public:
//    int takeAttendance(vector<int>& records) {
//        int left = 0, right = records.size() - 1;
//        while (left < right) {
//            int mid = left + (right - left) / 2;
//            if (records[mid] == mid)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        if (records[left] == left)
//            return left + 1;
//        return left;
//    }
//};